ডিসজয়েন্ট সেট (Disjoint Set) বা ইউনিয়ন-ফাইন্ড অ্যালগরিদম (Union-Find Algorithm) হল একটি ডেটা স্ট্রাকচার যা বিভিন্ন উপাদানের মধ্যে সংগঠন এবং সংযুক্তি পরিচালনা করতে ব্যবহৃত হয়। এটি সাধারণত গ্রাফ তত্ত্বে এবং বিভিন্ন সমস্যা সমাধানে ব্যবহৃত হয়, যেখানে উপাদানগুলি গোষ্ঠীভুক্ত করতে হয়।
মূল কাজ
ডিসজয়েন্ট সেট ডেটা স্ট্রাকচার মূলত দুটি মৌলিক কাজ সমর্থন করে:
- ফাইন্ড (Find): একটি উপাদানের রুট প্রতিনিধির সন্ধান করা। এটি যাচাই করে যে কোনও দুটি উপাদান একই গোষ্ঠীর অংশ কিনা।
- ইউনিয়ন (Union): দুটি উপাদানকে একত্রিত করে একটি নতুন গোষ্ঠী তৈরি করা।
কাজ করার প্রক্রিয়া
ডিসজয়েন্ট সেট অ্যালগরিদমের কাজ করার পদ্ধতি নিম্নরূপ:
প্রাথমিককরণ:
- প্রতিটি উপাদানকে একটি পৃথক গোষ্ঠীতে রাখুন। সাধারণত, একটি অ্যারে ব্যবহার করা হয় যেখানে প্রতিটি উপাদানের জন্য তার নিজস্ব রুট প্রতিনিধির নির্দেশ করে।
ফাইন্ড অপারেশন:
- একটি উপাদানের রুট খুঁজতে হলে, এটি শুরু করে তার পিতা (parent) পর্যন্ত যেতে হয়। এই প্রক্রিয়ায় পাথ কম্প্রেশন (Path Compression) ব্যবহার করা হয়, যেখানে মধ্যবর্তী নোডগুলিকে সরাসরি রুটের সাথে সংযুক্ত করা হয়, যাতে ভবিষ্যতে অনুসন্ধান দ্রুত হয়।
ইউনিয়ন অপারেশন:
- দুইটি উপাদান একত্রিত করতে, তাদের রুট খুঁজে বের করুন এবং নিম্ন র্যাঙ্কের গোষ্ঠীকে উচ্চ র্যাঙ্কের গোষ্ঠীর অধীনে সংযুক্ত করুন। এতে গোষ্ঠীটি সঠিকভাবে গঠিত হয় এবং ভারসাম্য বজায় থাকে।
টাইম কমপ্লেক্সিটি
- ফাইন্ড অপারেশন: \( O(\alpha(n)) \)
- ইউনিয়ন অপারেশন: \( O(\alpha(n)) \)
এখানে \( \alpha(n) \) হল ইনভার্সিড অ্যাক্সিস ফাংশন, যা খুব দ্রুত বৃদ্ধি পায় এবং তাই প্রায় ধ্রুবক হিসাবে বিবেচিত হয়।
উদাহরণ
ধরি আমাদের 5টি উপাদান (0 থেকে 4) রয়েছে:
প্রাথমিককরণ: প্রতিটি উপাদান আলাদা গোষ্ঠীতে রয়েছে:
0 1 2 3 4
ইউনিয়ন অপারেশন: 0 এবং 1 যুক্ত করুন:
0-1
2 3 4
ফাইন্ড অপারেশন: 1 এর রুট খুঁজুন, যা 0 হবে।
আরেকটি ইউনিয়ন: 3 এবং 4 যুক্ত করুন:
0-1
2 3-4
অবশেষে, 1 এবং 4 এর মধ্যে সংযোগ: 1 এবং 4 এর জন্য ফাইন্ড চালান, তারা সংযুক্ত কিনা যাচাই করুন।
ব্যবহার
ডিসজয়েন্ট সেট অ্যালগরিদমের বিভিন্ন ব্যবহার রয়েছে:
- গ্রাফের সংযোগ পরীক্ষা: গ্রাফে দুইটি নোড সংযুক্ত কিনা তা যাচাই করতে।
- মিনিমাম স্প্যানিং ট্রি: ক্রুস্কাল অ্যালগরিদমের মতো অ্যালগরিদমে, যেখানে একটি গ্রাফের মিনিমাম স্প্যানিং ট্রি তৈরি করতে হয়।
- ক্লাস্টারিং: বিভিন্ন ডেটা পয়েন্টকে একটি একক গ্রুপ বা ক্লাস্টারে সংযুক্ত করতে।
- ইনভলভমেন্ট ডিটেকশন: সামাজিক নেটওয়ার্ক বা অন্যান্য সিস্টেমে ব্যক্তি বা উপাদানের সংযোগ নির্ণয়ে।
উপসংহার
ডিসজয়েন্ট সেট বা ইউনিয়ন-ফাইন্ড অ্যালগরিদম একটি কার্যকরী এবং গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা গ্রাফ এবং নেটওয়ার্ক সমস্যা সমাধানে অত্যন্ত উপকারী। এটি সহজ এবং দ্রুতগতির কার্যকারিতার জন্য অনেক কম্পিউটার বিজ্ঞান ও বাস্তব জীবনের সমস্যা সমাধানে ব্যাপকভাবে ব্যবহৃত হয়।
